package com.algorithm4;

import java.util.Arrays;

public class HeapSort {

    public static void heapSort(int[] array,int len){
        buildHeap(array,len);//构建堆
        System.out.println("构建堆:" + Arrays.toString(array));
        //堆排
        for( int j = len;j>0;j--){
            swap(array,j,1);
            len--;
            heapify(array,len,1);
        }
        System.out.println("heapSort结果:" + Arrays.toString(array));
    }

    public static void buildHeap(int[] array,int len){
        for(int j=len/2;j>0;j--){
            heapify(array,len,j);
        }
    }

    public static void heapify(int[] array,int len,int i){
        int left = 2*i;
        int right = 2*i+1;
        int maxP = i;
        if(left<len && array[left] > array[maxP]){
            maxP = left;
        }
        if(right<len && array[right] > array[maxP]){
            maxP = right;
        }
        if(maxP != i){
            swap(array,i,maxP);
            heapify(array,len,maxP);
            System.out.println("i为："+"-->"+i +"-->"+ Arrays.toString(array));
        }
    }
    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    public static void main(String[] args){
        int[] array = new int[]{0,8, 9, 3,10, 2, 4, 5, 6, 7, 1};
        heapSort(array,array.length-1);
        //buildHeap(array,array.length-1);

    }


}
